 '''Fermat's little theorem''' (so named to distinguish it from Fermat's last theorem) states that if ''p'' is a prime number, then for any integer ''a'', ''a''&amp;nbsp;''p''&amp;nbsp;&amp;minus;&amp;nbsp;''a'' will be evenly divisible by ''p''. This can be expressed in the notation of modular arithmetic as follows:  :a^p \equiv a \pmod{p}.\,\!  A variant of this theorem is stated in the following form: if ''p'' is a prime and ''a'' is an integer coprime to ''p'', then ''a''&amp;nbsp;''p''&amp;minus;1&amp;nbsp;&amp;minus;&amp;nbsp;1 will be evenly divisible by ''p''. In the notation of modular arithmetic:  :a^{p-1} \equiv 1 \pmod{p}.\,\!  Fermat's little theorem is the basis for the Fermat primality test. The theorem is named after Pierre de Fermat.  ==History== Pierre de Fermat first stated the theorem in a letter dated October 18, 1640 to his friend and confidant Frénicle de Bessy as the following: [ ''p'' divides ''a''&amp;nbsp;''p''&amp;minus;1&amp;nbsp;&amp;minus;&amp;nbsp;1 whenever ''p'' is prime and ''a'' is coprime to ''p''.  As usual, Fermat did not prove his assertion, only stating:  Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long. (And this proposition is generally true for all progressions and for all prime numbers; the proof of which I would send to you, if I were not afraid to be too long.)  Euler first published a proof in 1736 in a paper entitled &quot;Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio&quot;, but Leibniz left virtually the same proof in an unpublished manuscript from sometime before 1683.  The term &quot;Fermat's Little Theorem&quot; was first used in 1913 in ''Zahlentheorie'' by Kurt Hensel:  Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.&quot;   (There is a fundamental theorem holding in every finite group, usually called Fermat's little Theorem because Fermat was the first to have proved a very special part of it.)  It was first used in English in an article by Irving Kaplansky, &quot;Lucas's Tests for Mersenne Numbers,&quot; ''American Mathematical Monthly'', '''52''' (Apr., 1945).  ===Further history===   Some mathematicians independently made the related hypothesis (sometimes incorrectly called the Chinese Hypothesis) that ''p'' is a prime if and only if 2^p \equiv 2 \pmod{p}\,. This is a special case of Fermat's little theorem. However, the &quot;if&quot; part of this hypothesis is false: for example, 2^{341} \equiv 2\pmod{341}\,, but 341&amp;nbsp;=&amp;nbsp;11&amp;nbsp;×&amp;nbsp;31 is a pseudoprime. See below.  ==Proofs==    Fermat gave his theorem without a proof. The first one who gave a proof was Gottfried Leibniz in a manuscript without a date, where he wrote also that he knew a proof before 1683.  ==Generalizations== A slight generalization of the theorem, which immediately follows from it, is: if ''p'' is prime and ''m'' and ''n'' are ''positive'' integers such that :m\equiv n\pmod{p-1}\,  then  \forall a\in\mathbb{Z} : \quad a^m\equiv a^n\pmod{p}.  This follows as ''m'' is of the form b(p-1)+ n, so a^{b(p-1)}\cdot a^{n}\equiv 1^{b}\cdot a^{n}\pmod{p}.  In this form, the theorem is used to justify the RSA public key encryption method.  Fermat's little theorem is generalized by Euler's theorem: for any modulus ''n'' and any integer ''a'' coprime to ''n'', we have :a^{\varphi (n)} \equiv 1 \pmod{n} where φ(''n'') denotes Euler's totient function counting the integers between 1 and ''n'' that are coprime to ''n''. This is indeed a generalization, because if ''n'' = ''p'' is a prime number, then φ(''p'') = ''p''&amp;nbsp;&amp;minus;&amp;nbsp;1.  This can be further generalized to Carmichael's theorem.  The theorem has a nice generalization also in finite fields.  ==Pseudoprimes== If ''a'' and ''p'' are coprime numbers such that ''a''&amp;nbsp;''p''&amp;minus;1&amp;nbsp;&amp;minus;&amp;nbsp;1 is divisible by ''p'', then ''p'' need not be prime. If it is not, then ''p'' is called a pseudoprime to base ''a''. F. Sarrus in 1820 found 341 = 11&amp;nbsp;×&amp;nbsp;31 as one of the first pseudoprimes, to base 2.  A number ''p'' that is a pseudoprime to base ''a'' for every number ''a'' coprime to ''p'' is called a Carmichael number (e.g. 561).  ==Converse== The converse of Fermat's little theorem is not generally true, as it fails for Carmichael numbers. However, a slightly stronger form of the theorem is true, and is known as Lehmer's theorem. The theorem is as follows: If there exists an a such that : a^{n-1}\equiv 1\pmod{n} and for all prime q dividing n-1 : a^{(n-1)/q}\not\equiv 1\pmod{n}  then n is prime.  This theorem forms the basis for the Lucas-Lehmer test, an important primality test.  